最大2-正则诱导子图的长度

设G是2-连通图，c(G)是图G的最长诱导圈的长度，c′(G)是图G的最长诱导2-正则子图的长度。本文我们用图的特征值给出了c(G)和c′(G)的几个上界。     

强色指数的一个新的上界

给出了图的强色指数的一个新的上界，并指出几类恰好达到该上界的图，从而改进了Erodoes和Nesetri的强色指数猜想，在某种意义上证明了这个猜想。     

Fully-angular polyhex chains with minimal total π-electron energy

By Hückel molecular orbital (HMO) theory, the calculation of the total energy of all π-electrons in conjugated hydrocarbons can be reduced to that of E(G)=|λ₁|+|λ₂|+?+|λn|, where λi are the eigenvalues of the corresponding graph G. Denote by Ψn the set of all fully-angular polyhex chains with n hexagons. In this paper, we show that Hn has the minimum total π-electron energy among chains in Ψn, where Hn is the helicene chain.     

Diameter graphs of polygons and the proof of a conjecture of Graham

We show that for an n-gon with unit diameter to have maximum area, its diameter graph must contain a cycle, and we derive an isodiametric theorem for such n-gons in terms of the length of the cycle. We then apply this theorem to prove Graham's 1975 conjecture that the diameter graph of a maximal 2m-gon (m?3) must be a cycle of length 2m−1 with one additional edge attached to it.     

最大度为6的极大外平面图的完备色数

证明了最大度为６的极大外平面图的完备色数为７。     

w-DENSITY AND w-BALANCED PROPERTY OF WEIGHTED GRAPHS

§ 1　IntroductionAll graphsconsidered in this paperare finite undirected ones withoutloops ormultipleedges.Our terminology and notation are standard exceptas indicated.A good reference forany undefined terms is[1 ] .Let G be a graph with vertex set V( G) and edge set E( G) .The density of G is definedbyd( G) =ε( G)ν( G) ,whereν( G) andε( G) denote| V( G) | and| E( G) | ,respectively.G is said to be balanced iffor each subgraph H of G we have d( H )≤ d( G) ,where V( H ) is assum…     

Bager第五图的完善

１９８９年发表的Ｂａｇｅｒ第五图，包含关于三角形元素的３５个二次规范画数之间的５１个不等式通过细致的分析，本文给出了其中遗漏的１２个基本不等式     

一类几乎最优循环图{C_p(m,m+1,p/a)}

本文比较了循环图类{c_p(n_1,…,n_p)}和{c-p(n_1…,n_p,p/α)}的直径下界。对于p和α满足一定条件的循环图类{c_p(n_1,n_2,p/α)},本文给出了达到或几乎达到此图类直径下界的一类几乎最优循环图{c_p(m,m+1,p/α)}。     

Combinatorial Optimization by Dynamic Contraction

A heuristic optimization methodology, Dynamic Contraction (DC), is introduced as an approach for solving a wide variety of hard combinatorial problems. Contraction is an operation that maps an instance of a problem to a smaller instance of the same problem. DC is an iterative improvement strategy that relies on contraction as a mechanism for escaping local minima. As a byproduct of contraction, efficiency is improved due to a reduction of problem size. Effectiveness of DC is shown through simple applications to two classical combinatorial problems: The graph bisection problem and the traveling salesman problem.     

A graph theory approach to subcontracting, machine duplication and intercell moves in cellular manufacturing

We address in this paper the problem of finding an optimal strategy for dealing with bottleneck machines and bottleneck parts in the cell formation process in group technology. Three types of economic decisions are considered: subcontracting, machine duplication and intercell moves. The problem is formulated as a minimum weighted node covering problem in a hypergraph, and we show that it can be solved in polynomial time by finding a maximum weighted stable set in a bipartite graph. We extend this result to cellular manufacturing systems in which the sequence of operations of each part is known in advance.